﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}
	PrevOrder(root->left);
	printf("%d ", root->data);
	PrevOrder(root->right);
}
//后续遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}
	PrevOrder(root->left);
	PrevOrder(root->right);
	printf("%d ", root->data);
}
//层次遍历
void LevelOrder(BTNode* root) 
{
	if (root == NULL) 
		return;

	BTNode* queue[1000];   // 定义队列，最多存放1000个节点

	int head = 0, tail = 0;
	queue[tail++] = root;
	while (head < tail) 
	{
		BTNode* curNode = queue[head++];   // 出队

		printf("%d ", curNode->data);

		if (curNode->left != NULL)
			queue[tail++] = curNode->left;    // 左孩子入队

		if (curNode->right != NULL)
			queue[tail++] = curNode->right;   // 右孩子入队
	}
}


//手动构建一个树
BTNode* BuyBTNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

//求二叉树总结点数：
int size = 0;//定义全局变量
void TreeSize1(BTNode* root)
{
	if (root == NULL)
		return;

	size++;
	TreeSize1(root->left);
	TreeSize1(root->right);
}
//更优解：
int TreeSize2(BTNode* root)
{
	return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

//求叶子结点的个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

//求树的深度/高度
int TreeHeight(BTNode* root)
{
	//if (root == NULL)
	//{
	//	return 0;
	//}
	// // 这种写法十分浪费资源，会有很多重复的计算
	//return TreeLeafSize(root->left) > TreeLeafSize(root->right) ? 
	//	TreeLeafSize(root->left) + 1 : TreeLeafSize(root->right) + 1;
	if (root == NULL)
	{
		return 0;
	}
	//保留算出的数据，防止重复计算比较
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//求第K层的结点数 k>=1
int TreeKLevelSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	// k > 1 子树的k-1
	return TreeKLevelSize(root->left, k - 1)
		+ TreeKLevelSize(root->right, k - 1);
}

//二叉树查找值未x的节点 
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;
}

//判断二叉树是否为完全二叉树：
bool isCompleteTree(BTNode* root)
{
	BTNode* queue[1000];  //直接用树的结构来生成一个队列（只用到data变量，不用到左右孩子）

	int head = 0, tail = 0;    //head即队列的头节点，用来出数据，tail即队列的尾结点，用来入数据

	bool flag = false;      // 存储是否出现过空节点的标记

	queue[tail++] = root;   //先让队列的头=树的根节点

	while (head < tail) 
	{
		BTNode* curNode = queue[head++];
		
		//在第一次遇到NULL的时候，用flag进行记录
		if (curNode == NULL)
			flag = true;
		else 
		{
			if (flag)        // 如果之前出现过空节点，说明当前节点不是完全二叉树的节点
				return false;
			queue[tail++] = curNode->left;
			queue[tail++] = curNode->right;
		}
	}
	return true;
}

void destroyTree(BTNode* root)
{
	if (root == NULL)
		return;
	destroyTree(root->left);
	destroyTree(root->right);
	free(root);
}

int main()
{
	BTNode* root;

	BTNode* n1 = BuyBTNode(10);
	BTNode* n2 = BuyBTNode(8);
	BTNode* n3 = BuyBTNode(6);
	BTNode* n4 = BuyBTNode(12);
	BTNode* n5 = BuyBTNode(9);
	BTNode* n6 = BuyBTNode(15);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	/*BTNode* n7 = BuyBTNode(7);
	n2->right = n7;*/


	printf("前序遍历：\n");
	PrevOrder(n1);
	printf("\n");

	printf("中序遍历：\n");
	InOrder(n1);
	printf("\n");

	printf("后续遍历：\n");
	PostOrder(n1);
	printf("\n");

	printf("层次遍历：\n");
	LevelOrder(n1);
	printf("\n");

	printf("\n\n\n");

	//打印总结点个数
	size = 0;  //size是全局变量，每次使用前都需要手动置0,否则会在之前的基础上再加
	TreeSize1(n1);
	printf("TreeSize1：%d\n", size);

	TreeSize1(n1);
	printf("TreeSize1（size未置0）：%d\n", size);

	size = 0;
	TreeSize1(n1);
	printf("TreeSize1（重新将size置0）：%d\n", size);

	printf("\n\n\n");

	printf("TreeSize2：%d\n", TreeSize2(n1));
	printf("TreeSize2：%d\n", TreeSize2(n1));
	printf("TreeSize2：%d\n", TreeSize2(n1));


	//打印叶子结点
	printf("叶子节点个数：%d\n", TreeLeafSize(n1));

	//打印树的高度
	printf("数的高度：%d\n", TreeHeight(n1));
	
	//计算第k层的结点：
	printf("数k层的结点个数：%d\n", TreeKLevelSize(n1,4));

	//二叉树查找值未x的节点 
	BTNode* cur = TreeFind(n1, 8);
	printf("：%d\n", cur->data);

	//判断二叉树是否为完全二叉树：
	if (isCompleteTree(n1))
	{
		printf("是完全二叉树\n");
	}
	else
	{
		printf("不是完全二叉树\n");
	}

	destroyTree(n1);

	return 0;
}